package puzzle.projecteuler.p200;

import java.util.Arrays;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Set;


public class Problem122B {

	/**
	 * 
	 * 问题的思路比较简单，关键是如何提高速度和减少使用的内存。
	 * 
	 * 目前只是简单遍历，应该不能用动态规划的方法解决。
	 * 
	 * 
	 * @param args
	 */
	public static void main(String[] args) {

		long s = System.currentTimeMillis();
		int[] tmp = calc(200);
		int sum = 0;
		for (int i = 0; i < tmp.length; i ++) {
			System.out.println(i + "\t" + tmp[i]);
			sum += tmp[i];
		}
		System.out.println("sum = " + sum);
		System.out.println((System.currentTimeMillis() - s) + " ms");
	}
	
	public static int[] calc(int k) {
		int[] m = new int[k+1];
		m[0] = 0;
		m[1] = 0;
		for (int i = 2; i < m.length; i ++) {
			m[i] = -1;
		}
		int c = 2;
		LinkedList<int[]> q = new LinkedList<int[]>();//记录中间产生的所有序列
		q.add(new int[] {1});
		while (c < k+1) {
			int[] tmp = q.removeLast();
			Set<Integer> newTerms = new HashSet<Integer>();
			for (int i = 0; i < tmp.length; i ++) {
				//tmp[0]中保存的是该序列中最新加入的元素，
				//下一个新增元素一定是某个tmp[i]与tmp[0]的和，
				//而不用遍历所有tmp[i]+tmp[j],
				//这样一来可以减少中间序列的数目，二来可以减少重复的中间序列
				int newTerm = tmp[i] + tmp[0];
				if (Arrays.binarySearch(tmp, newTerm) < 0) {
					newTerms.add(newTerm);
				}
			}
			for (Integer newTerm: newTerms) {
				if (newTerm <= k) {
					int[] newTmp = new int[tmp.length+1];
					newTmp[0] = newTerm;
					System.arraycopy(tmp, 0, newTmp, 1, tmp.length);
					q.add(newTmp);	//这里千万不要为newTmp排序，以确保newTmp[0]中保存是最新的数据
					if (m[newTerm] == -1) {
						c ++;
						m[newTerm] = tmp.length;
//						System.out.println(newTerm + ":" + newTmp);//这里打印产生newTerm最佳算法对应的序列
					}
				}
			}
		}
//		System.out.println(q.size());//中间序列的数据还是很庞大的
		return m;
	}
}
